package com.cwj.lab1;

import com.cwj.lab4.Tool;

import java.util.Arrays;
import java.util.Comparator;
/**
 * myArrayList
 * 顺序存储结构的线性表
 * */
public class myArrayList<T>implements Cloneable {
    //存放线性表元素的数组
    private Object[]nums;
    //数组长度，其实java中，因为数组为对象，所以其长度可以获取的，但是在C++/C语言中，是需要额外添加的
    private int MAX_SIZE;
    //有效元素个数，即前len个元素
    private int len;

    private static final Object[] EMPTY_LIST={};

    /**
     * 无参构造器初始化后为空表
     * */
    public myArrayList() {
        nums=myArrayList.EMPTY_LIST;
    }
    /**
     * @param size 指定nums的长度
     * */
    public  myArrayList(int size) {
        if(size>0){
            this.nums = new Object[size];
            this.len = 0;
            MAX_SIZE = size;
        }
        else if(size==0) nums=myArrayList.EMPTY_LIST;
        if(size<0)throw new RuntimeException("myArrayList有参构造其参数不小于0");

    }
    /**
     * 改变容量操作
     * 注意：不一定为扩容操作，也可能为缩小操作，其不会进行长度检查，故可能会导致数据丢失，需要谨慎
     * @param size 即将nums数组的长度变为为size;且将原数组的元素都复制过去
     * */
    private void resize(int size){
        Object[]Nums=new Object[size];
        //也可采用一些现有的函数，其是native方法，一些更有效率的语言的实现效率会更快一些
        //if (len >= 0) System.arraycopy(nums, 0, Nums, 0, len);
        //注意这里没有保证说所以有效的元素一定会被加入，所以这个函数也可以做为缩小操作
        for(int i=0;i<len&&i<Nums.length;i+=1){
            Nums[i]=nums[i];
        }
        this.MAX_SIZE=size;
        this.nums=Nums;
        //如果为C++在这里就需要释放内存空间
    }
    /**
     * 对有参resize函数的限制，将其简化为一个特殊的扩容操作
     * 要么数组添加1，要么增加this.len/2,取较大值
     * */
    private void resize(){
        if(this.len>=this.MAX_SIZE)
        resize(Math.max(1,this.len>>1)+this.len);
    }
    /**
     * 获取元素，因为java的泛型有类型擦除机制，所以T最后会被变为Object,即该函数编译后会变为(T)Object get(int ind);
     * (T)为强制只有在需要用返回值进行赋值操作时，才会自动插入(T);但是return语句就不会查找，所以会出现Object被赋值给T
     * 类型对象的情况，程序会发出警告，所以需要@SuppressWarnings("unchecked")；后面如果出现这句话就道理基本一样；
     * 在java的ArrayList类中的get函数也用到了该做法
     * */
    @SuppressWarnings("unchecked")
    public T get(int ind){
        return (T)nums[ind];
    }
    /**
     * 在元素最后后面添加一个元素
     * @param data 新元素值
     * */
    public void addLast(T data){
        //检测是否还有空间
        this.resize();
        nums[len++]=data;
    }
    /**
     * 插入操作
     * @param ind 插入位置的索引，注意这里有0开始，区间【0，len-1】
     * @param data 新元素的值
     * */
    public void insert(T data,int ind){
        //检测是否还有空间
        this.resize();
        checkIndex(ind);
        for(int i=len;i>ind;i-=1){
            //因为前面已经有确保ind>=0且i>ind所以i-1一定为合法值
            nums[i]=nums[i-1];
        }
        nums[ind]=data;
        len+=1;
    }
    /**
     * 删除元素
     * @param ind 要删除元素的索引
     * @return 返回被删除元素的值
     * */
    public T del(int ind){
       checkIndex(ind);
       @SuppressWarnings("unchecked")
       T oldValue=(T)nums[ind];
       //边界i<len-1为保证i+1也在合法范围内
        for (int i = ind; i <len-1 ; i++) {
            nums[i]=nums[i+1];
        }
        len-=1;
        //删除操作后数组的len位置为删除操作前nums[len-1]的位置，现在的数组nums[len-1]=nums[len];
        //如果是在中间被删除的，那么因为引用的值会被后面的元素覆盖，使得被删除的元素可用被垃圾回收机制回收，
        //但是如果是删除len-1位置的元素，那么其仅仅只会进行len-=1;而最后一个元素的引用还在，导致元素不会被垃圾回收机制回收，导致内存浪费
        //当然如果后面可用保证在短时间内会添加元素的话，确实可以保证不会出现这种情况，但是最后在删除后，将第一个无效元素位置置为null
        nums[len]=null;
        return oldValue;
    }
    /**
     * 删除最后一个元素
     * @return 返回被删除元素的值
     * */
    @SuppressWarnings("unchecked")
    public T delLast(){
        checkEmpty();
        T oldVal=(T)this.nums[len-1];
        this.nums[len-1]=null;//让垃圾回收机制可以回收该对象空间
        len-=1;
        return oldVal;
    }
    /**设置，将索引值nums[ind]设置为data
     * @param ind 位置
     * @param data 新值
     * */
    public void set(int ind,T data){
        checkIndex(ind);
        nums[ind]=data;
    }
    //该函数仅在删除，访问等函数中有使用
    //所以该函数不对外开放
    private void checkEmpty(){
        if(len<=0){
            throw new RuntimeException("数组为空");
        }
    }

    //检查是否越界
    //该函数不对外开放
    private void checkIndex(int ind){
        //检测ind的合法性
        if(ind<0||ind>=len){
            throw new RuntimeException("索引越界");
        }
    }
    /**
     * 二分查找:前提是必须有序才会有效，且默认为升序排序
     *参数需要传入一个比较器，因为我们没有保证T有没有实现正确的Comparable接口，所以这里强制传入
     * @param target 要查找的值
     * @param comparator 比较器
     * */
    @SuppressWarnings("unchecked")
    public int binarySearch(T target, Comparator<T>comparator){
        int lef=0,rig=len-1;
        int temp=0;
        while(lef<rig){
            int mid=lef+((rig-lef)>>1);
            temp=comparator.compare(target,(T)nums[mid]);
            if(temp<0){
                rig=mid-1;
            }else if(temp>0){
                lef=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    /**
     * 数组长度
     * */
    public int size(){
        return len;
    }
    /**
     * 是否为空
     * */
    public boolean isEmpty(){
        return len==0;
    }
    public T back(){
        checkEmpty();
        return get(len-1);
    }
    /**
     * 反转线性表
     * */
    public void reserve(){
        int lef=0,rig=this.len-1;
        while(lef<rig){
            Tool.swap(this.nums,lef++,rig--);
        }
    }
    /**
     * 查找
     * */
    public int find(T data){
        for(int i=0;i<this.len;i+=1){
            if(data.equals(this.nums[i])){
                return i;
            }
        }
        return -1;
    }
    /**
     * 遍历表，并打印，一般用于调试
     * 因为是泛型编程，所以T类型元素想正确显示就需要实现正确的toString函数
     * */
    public void show(){
        System.out.print("{");
        for (int i = 0; i < len; i++) {
            System.out.print(this.get(i)+" ");
        }
        System.out.print("}");
        System.out.print("\tsize="+this.size());
        System.out.println();
    }
    /**
     * 功能就是将数组元素转化为可表示的字符串，一般用于比较和显示
     * 注意：T类型元素需要重写正确的toString函数
     * */
    @Override
    public String toString() {
        return "myArrayList{" +
                "nums=" + Arrays.toString(nums) +
                ", MAX_SIZE=" + MAX_SIZE +
                ", len=" + len +
                '}';
    }
    /**
     * 克隆这个数组，该函数很少用到，之所以要写他是因为有时再搜索，
     * 或是记录路线问题中，该函数就很有用
     * */
    @Override
    public Object clone() throws CloneNotSupportedException {
        myArrayList<?>newList=(myArrayList<?>) super.clone();
        newList.nums=Arrays.copyOf(this.nums,this.len);
        newList.len=len;
        newList.MAX_SIZE=len;
        return newList;
    }


    //测试myArrayList类
    public static void main(String[] args) {
        myArrayList<Integer>list=new myArrayList<>();
        for (int i = 0; i < 50; i++) {
           if(choose(list,(int)(Math.random()*20),(int)(Math.random()*list.size()),(int)(Math.random()*5)))
           list.show();
        }
    }
    //测试函数：随机选出一个操作
    public static boolean choose(myArrayList<Integer>list,int data,int ind,int cho){
        switch (cho){
            case 0:
                System.out.print("数组末尾添加元素："+data+"-->");
                list.addLast(data);
                break;
            case 1:
                if(list.isEmpty()) return false;
                System.out.print("数组在"+ind+"索引处插入"+data+"-->");
                list.insert(data,ind);
                break;
            case 2:
                if(list.isEmpty()){
                    return false;
                }
                System.out.print("数组删除末尾元素"+list.back()+"-->");
                list.delLast();
                break;
            case 3:
                if(list.isEmpty())return false;
                System.out.print("数组删除"+ind+"索引处"+list.get(ind)+"-->");
                list.del(ind);
                break;
            case 4:
                System.out.print("反转数组：");
                list.reserve();
                break;
        }
        return true;
    }

    public void clear(){
        this.len=0;
    }


}
